/*
 * @Author: your name
 * @Date: 2021-11-08 21:57:47
 * @LastEditTime: 2021-11-08 22:19:59
 * @LastEditors: Please set LastEditors
 * @Description: 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 * @FilePath: \DAA\Maximum_Contiguous_Subarray\exhaustion.c
 */

// O(N3)

// -2, 11, -4, 13, -5, -2

#include <stdio.h>
#include <stdlib.h>

// A: Array, N: Size of A
int MaxSubsequenceSum(const int A[], int N)
{
    int ThisSum, MaxSum, i, j, k;
    MaxSum = 0;
    for (i = 0; i < N; i++)
    {
        /* code */
        for (j = i; j < N; j++)
        {
            /* code */
            ThisSum = 0;
            for (k = i; k <= j; k++)
            {
                /* code */
                ThisSum += A[k];
            }
            
            if (ThisSum > MaxSum)
            {
                /* code */
                MaxSum = ThisSum;
            }
            
        }
        
    }
    
    return MaxSum;
}


int main(int argc, char const *argv[])
{
    int A[] = {-2, 11, -4, 13, -5, -2};
    printf("The Max Sum is: %d\n", MaxSubsequenceSum(A, 6));

    return 0;
}
